The invention relates to a multistage decoder for decoding received symbols coded into blocks formed by symbols which are consecutively emitted after having undergone a multilevel coding according to several successive partitioning levels from a constellation into several subsets during an emission, a symbol of the constellation being coded by means of several bits, while each stage of the multistage decoder determines a sequence of bits relative to a partitioning level for a sequence of estimated symbols which are selected from among the symbols of the constellation or the subset as being each individually the closest to the received symbols, a stage comprising decision means followed by a stage decoder and being validated in cascade fashion by the outputs of the preceding stages in the order of succession of the said levels.
Such a decoder is used in the transmission of digital signals through a transmission channel.
This may relate to the transmission of digital television signals, for example high-definition, through a satellite channel, or digital signals through radio beams. It may alternatively relate to the transmission of sound by mobile radio, or digital data to be stored, for example, in a Compact Disc or digital video recorder. In these cases, it is necessary to carry out a preliminary reduction of the output rate at the source by a source encoder during the emission, and to re-establish the output rate at the receiving end by means of a source decoder. This rate reduction by a source encoder is not necessary in the case in which digital data are to be transmitted between two digital processing units, for example, between two calculators.
Since the most representative application is that of high-definition television (HDTV), for which the problems are the most wide-ranging, the present Patent Application is drawn up with reference to this technical application without any limitation whatsoever being implied thereby.
The digitization of high-definition television (HDTV) signals involves a total gross output rate of the order of 800 Mbits/s. The transmission of such information with such an output rate cannot be economically realised through existing transmission channels. Several coding techniques for reducing the output rate (source coding) have been developed. The performance levels of these coding algorithms are measured in terms of their "reduction factor" of the output rate and the quality of the restored image after decoding. The more the redundancy of the signal is reduced, the more the transmitted information is significant. Possible transmission errors which may be corrected fairly easily when the transmitted information is redundant have consequences of increasing gravity in proportion as the reduction factor increases.
As a result, the transmission of digital HDTV signals necessitates a suitable protection. If the effects of transmission errors should not be visible on a screen, the error rate per line must be lower than 10.sup.-11.
The channel used for "Direct Broadcasting by Satellite" (DBS) has the following characteristics:
a bandwidth of 27 MHz, PA1 a low power (especially for the signal coming from the satellite) and the presence of a high noise level, which can be considered as additive, white and Gaussian, and PA1 non-linear distortions. PA1 either the erasure bit, PA1 or the bit of the symbol closest to the received symbol, depending on whether the received symbol is or is not situated in an erasure zone. PA1 a detector which supplies a bit of the said estimated symbol for each received symbol, PA1 a comparator which compares the sequence of positions of the estimated symbols with at least one boundary position which defines the erasure zones, PA1 an erasure generator PA1 a counter which counts the number NE of erasure bits of a block of estimated bits, PA1 an adaptation member which, if the number NE is higher than a limit value q, modifies the boundary position of the comparator so as to reduce the width of the erasure zones, and which maintains the boundary position in the opposite case.
The transmission of digital HDTV signals through such a channel requires a source coding with a considerable degree of compression as well as a digital modulation with a high spectral efficacy.
The source coding techniques, for example, based on an orthogonal transformation, are capable of reducing the output level by a factor 10 while still providing a good quality of the restored image. This leads to the transmission of a binary output of the order of 70 Mbits/s. However, the transmission of such signals through a satellite channel requires a digital modulation with a spectral efficacy of up to 3 bits/s/Hz.
Furthermore, it is necessary to carry out a channel coding to protect the transmission from the imperfections of the channel. The classical coding and modulation techniques are found to have their limitations as regards full compliance with the requirements of a correct transmission (in these techniques, the coding function is regarded as an entity which is independent of the modulation function). The coding techniques, however, have been considerably improved thanks to the coding technique proposed by G. UNGERBOECK in the article "Channel Coding with Multilevel/Phase Signals" published in IEEE Transactions on Information Theory, vol. IT-28, no. 1, January 1982, pp. 55-67.
It is proposed to consider the channel coding and the modulation as one entity and to combine for this purpose a channel coding with a digital modulation. This renders it possible to increase the efficacy of the digital transmission, so to improve the performance, without sacrificing the spectral efficacy. The additional redundancy induced by the coding is transmitted through the redundancy of the alphabet instead of diminishing the data rate. This technique is based on the principle of maximizing the minimum Euclidean distance between the sequences of transmitted coded symbols.
Thus, after a coding step which transforms p bits of information into m bits, with m&gt;p, in which m-p represents the added redundancy for information protection during transmission, with a modulation of 2.sup.m states, there are 2.sup.m-p extra states available for transmitting this redundancy. This modulation technique renders it possible to carry out a spatial, not temporal partitioning of the redundancy.
Following the discovery by G. UNGERBOECK, trellis-coded modulations (TCM), block-coded modulations (BCM) and multidimensional trellis-coded modulations have been proposed.
TCM of medium complexity (4 or 8 states) are capable of providing a coding gain of 3 to 4 dB. For large-scale applications, however, the addition of a Viterbi decoder necessary for decoding these TCM remains expensive with present-day technology. An attractive coding technique for these applications is that of multilevel coding. The interest of this technique lies in that it is adapted to a simple process of sub-optimal decoding which takes place in steps and offers a good compromise between performance and implementing complexity.
Based on the set partitioning principle as disclosed by G. UNGERBOECK, the use of multilevel coding has been analyzed in particular by G. J. POTTIE and D. P. TAYLOR in "Multilevel Codes Based On Partitioning" IEEE Trans. Information Theor., vol. 35, no. 1, January 1989, pp. 87-98.
In their article, these authors first of all analyze the principle of multilevel coding which consists in partitioning a constellation and coding the symbols of the constellation, and secondly define a multistage encoder, a coding stage being assigned to a partitioning level, while the symbols are transmitted in blocks through a transmission channel.
At the receiving end, a multistage decoder carries out the inverse operation and restores the symbols corresponding to the emitted symbols. In a classical decoder, this involves decision operations which estimate the symbols and determine bits for the codes of the estimated symbols as a function of the phase and the amplitude detected at the receiving end for each received symbol. Depending on the various transmission and reception conditions, some of the estimated bits are incorrect. A first stage of the multistage decoder takes decisions at the first partitioning level. The result delivered by this first stage is used for enabling the operation of the second stage, and so on, until the last stage. In the article by G. J. POTTIE and D. P. TAYLOR, a supplementary concept of erasure is introduced, which takes place after each decoding of a stage, in a concatenated decoding operation. This improves the performance of the decoder, but at the price of an increased complexity. In fact, this necessitates the addition of a second decoder for correcting the errors and filling up the erased positions.